//数据流中的中位数
class MedianFinder {
public:
    struct comp {
        bool operator()(const int& x, const int& y) { return x > y; }
    };
    priority_queue<int> l_h;
    priority_queue<int, vector<int>, comp> r_h;
    int size = 0;
    /** initialize your data structure here. */
    MedianFinder() {}

    void addNum(int num) {
        int m = l_h.size(), n = r_h.size();
        size++;
        if (m == n) {
            if (m == 0 || num <= l_h.top()) {
                l_h.push(num);
            } else {
                r_h.push(num);
                l_h.push(r_h.top());
                r_h.pop();
            }
        } else {
            if (num > l_h.top()) {
                r_h.push(num);
            } else {
                l_h.push(num);
                r_h.push(l_h.top());
                l_h.pop();
            }
        }
    }

    double findMedian() {
        if (size % 2)
            return l_h.top();
        return (l_h.top() + r_h.top()) / 2.0;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

 //733. 图像渲染
 class Solution {
public:
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc,
                                  int color) {
        queue<pair<int, int>> q;
        int m = image.size();
        int n = image[0].size();
        vector<vector<bool>> hash(m, vector<bool>(n, false));
        q.push({sr, sc});
        int target = image[sr][sc];
        hash[sr][sc] = true;
        while (q.size()) {
            int x = q.front().first;
            int y = q.front().second;
            image[x][y] = color;
            for (int i = 0; i < 4; i++) {
                if (x + dx[i] >= 0 && x + dx[i] < m && y + dy[i] >= 0 &&
                    y + dy[i] < n && hash[x + dx[i]][y + dy[i]] == false) {
                    if (image[x + dx[i]][y + dy[i]] == target) {
                        q.push({x + dx[i], y + dy[i]});
                        hash[x + dx[i]][y + dy[i]] = true;
                    }
                }
            }
            q.pop();
        }
        return image;
    }
};